This invention relates to machine vision systems for object location and inspection and, more particularly, to techniques for fixturing targets.
In many applications, it is necessary to determine the two-dimensional location or translation and angular orientation of an object of interest. Depending on the application, a determination of one or more of these properties is called determining the xe2x80x9calignmentxe2x80x9d of an object. In some applications, alignment also may include additional degrees of freedom, such as scale, aspect, shear or even various types of non-linear deformations. For example, in a robotic assembly system, it may be necessary to determine the alignment of a printed circuit board so that a robotic arm can place an integrated circuit onto the board at a precise location. One way to perform this alignment is to mechanically constrain the board at a predetermined location and angular orientation. Guides, brackets and many other well-known mechanical arrangements can be used to accomplish this alignment. However, in other applications, it is not feasible to mechanically constrain each object. In these latter systems, machine vision systems are often used to determine the alignment of objects.
Machine vision systems acquire images of an environment, process the images to detect objects and features in the images and then analyze the processed images to determine characteristics of objects and other features detected in the images. The system generally includes a camera/frame grabber system that generates an image that consists of a plurality of digitized image pixels. The image pixels are then processed with an algorithm implemented in software and/or hardware typically called a vision xe2x80x9ctool.xe2x80x9d These systems can be used to determine the alignment of objects, such as printed circuit boards.
One way to perform this alignment is to acquire an image of the entire object and then use the vision system to determine the alignment of the object. However, since some objects can be quite large, the image acquisition apparatus may not be able to acquire an image of the entire object. Thus, the image may be constrained to only a portion of the object at any one time. Further, even if the entire image can be acquired at once, the processing time required to process the large image might be prohibitive. Also, examining only a portion of the entire image allows the alignment procedure to ignore substantial variations in the object in regions outside the selected portion; for example, circuit boards with different circuit trace patterns could be treated equivalently so long as the selected portions were similar or had similar identifying marks.
Consequently, in many applications, the alignment of an object is determined by examining only selected areas of the object. In order to facilitate this examination xe2x80x9cfiducialxe2x80x9d marks are placed on the object in the selected areas. These marks might comprise one or more small circles, squares or other shaped marks, where the shape is selected so that it would not occur on the object for any reason other than a fiducial mark. Then, the machine vision system can be instructed to examine the selected areas of the object and to locate the fiducial marks within these areas. The marks assist in determining the alignment of the object because they are in predetermined location is on the object.
Although fiducial marks work well, the alignment problem is complicated because the fiducial marks are generally placed on the object during the manufacture of the object. For example, fiducial marks can be placed on a printed circuit board by etching the marks into the board during the circuit board manufacturing process. However, manufacturing tolerances can distort or degrade the marks. In the case of etching, the etching process can change the original size of the mark if the edges of the mark are over etched or the mark can be distorted during the etching process, which distortion might, for example, distort a circular mark into an oval-shaped mark. Also, the angular orientation of the object, and thus of the fiducial mark on the object, with respect to the camera may not be precisely known. Therefore, the vision tool used to locate the marks must be capable of tolerating some variations in size, shape and angular orientation and still locate the mark.
The manner of determining the alignment of the object depends on the type of vision tool used to locate the marks. Some tools can tolerate variations in size, shape and angular orientation during the location procedure, but have other deficiencies. For example, the earliest vision tool widely used for object location and inspection in industry was blob analysis. In this type of tool, image pixels are classified as object or background pixels by some means, the object pixels are joined to make discrete sub-objects using neighborhood connectivity rules, and various moments of the connected sub-objects are computed to determine object position, size, and orientation. Blob analysis tools can tolerate and measure variations in orientation and size.
However, such tools cannot tolerate the presence of various forms of image degradation. A more serious problem was that the only generally reliable method ever found for separating object pixels from background pixels was to arrange for the objects to be entirely brighter or entirely darker than the background. This requirement is difficult to achieve in other than the most controlled conditions.
In order to overcome the limitations of blob analysis tools, techniques called xe2x80x9ctemplate matchingxe2x80x9d tools were developed to locate objects based on their pattern rather than grayscale intensities. A template matching tool typically starts with a training step. In this step, a software representation called a pattern, or template, of an image or synthetic description of an ideal object is created and stored. At run-time, the template is moved in various positions over the digitized image and compared to like-sized pixel subsets of the image. The position where the best match between the template and image sub-set pixels occurs is taken to be the position of the object. Because a xe2x80x9csearchxe2x80x9d is performed for the best match, this type of tool is often called a search tool. The degree of match (a numerical value) can be used for inspection, as can comparisons of individual pixels between the template and image at the position of best match.
The first template matching tools used a brightness threshold to reduce the pixels of the template and image to two states: xe2x80x9cbrightxe2x80x9d and xe2x80x9cdark.xe2x80x9d This reduced the computation necessary for the comparison operation to a reasonable level for the available computation facilities. Unfortunately, the thresholding step made sub-pixel accuracy impractical and made the results highly susceptible to the selection of the threshold and variations in illumination and object reflectivity.
Later tools overcame the thresholding problem by using a normalized correlation operation for the template and image comparison step, albeit at the cost of considerable additional computation. Normalized correlation template matching tools also overcame many of the limitations of blob analysis toolsxe2x80x94they can tolerate touching or overlapping objects, they perform well in the presence of various forms of image degradation, and the normalized correlation match value is useful in some inspection applications. Most significantly, perhaps, in order for the tool to operate properly, objects need not be separated from background by brightness, enabling a much wider range of applications.
Unfortunately, while normalized correlation template matching tools work well in determining the location of objects that are translated, they will tolerate only small variations in angular orientation and size: typically a few degrees and a few percent (depending on the specific template). Even within this small range of orientation and size variation, the accuracy of the results falls off rapidly when the objects deviate from fixed sizes and orientations and such a system may not be able to distinguish between two objects that do not differ much in size.
Other search tools have been devised that can determine the alignment of objects in the presence of variations in one or more other characteristics or xe2x80x9cdegrees of freedomxe2x80x9d in addition to translation. For example, such tools may be able to determine the alignment of objects in the presence of significant variations in translation and rotation, translation and size or translation and skew. Other tools can determine the alignment of objects in the presence of variations in multiple degrees of freedom, such as variations in translation, rotation and size. These tools can be used to locate objects in the presence of such variations.
For example, normalized correlation matching tools have been extended to tolerate variations in several degrees of freedom by using multiple templates in the search. In order to accommodate objects that vary in size, a separate template for each object size is created and stored during the training process. Similarly, in order to accommodate objects that have been rotated, a separate template is created for each object that is rotated with a different degree of rotation.
However, with such tools, a separate pattern must be trained for each object size and each orientation of each object size, and then a search must be performed using each pattern over the entire runtime image. Each pattern occupies computer memory, and, depending on the techniques and the size or complexity of the training image or description, a typical pattern may occupy tens or hundreds of kilobytes or even several megabytes of memory. Aside from the training time required to create the patterns, a large number of patterns can easily consume large amounts of memory. If the patterns are stored in a central location and downloaded to local computers when needed, the network connecting the computers must have significant bandwidth. Further, the need to search the image with a large number of patterns increases the search time significantly. In addition, because patterns must be created for each size and rotation, the patterns are created in discrete steps and the accuracy of the system suffers.
Still other search tools use geometric feature matching to locate and determine the alignment of objects with variations in several degrees of freedom, such as translation, rotation and size. In these systems, a feature detection algorithm produces a geometric description of object boundaries. This geometric description comprises a set of boundary points that lie along contours separating dissimilar regions in the image. Each boundary point specifies both position and orientation. In this system, the training process uses a training pattern to select features to represent the object. Once the boundary points have been generated, they can be transformed by parameterized mathematical algorithms to produce translated, rotated, scaled, and stretched patterns. The pattern search is thereby reduced to searches over parameter values. An example of such a system is the PatMax(copyright) search tool developed and sold by Cognex Corporation, One Vision Drive, Natick, Mass.
Other vision tools are available that can locate and determine the alignment of objects with variations in several degrees of freedom. These vision tools include the HexSight(copyright) Locator machine vision system developed and sold by Adept Technology, Inc., San Jose, Calif. and SMART Search(copyright) machine vision system developed and sold by Imaging Technology, Inc., 55 Middlesex Turnpike, Bedford, Mass. 01730.
In order to accommodate vision tools that do not tolerate variations in size and angular orientation well, fiducial marks are typically arranged to have rotational symmetry. For example, a small circle may be used. In this manner, the vision tool can still locate the fiducial mark although the mark may appear rotated in the image, as might be the case if the object were not fixtured with respect to the camera. Because the fiducial marks have rotational symmetry, once a mark is located, it cannot be used to determine the rotational alignment of the object on which it is located. Therefore, it is common practice to use two fiducial marks. Once both marks have been located, the rotational alignment of the object can be determined.
In order to increase the accuracy of the determination of rotational alignment using two marks, the marks are usually separated by a significant distance. For example, the marks might be located at opposite ends of an object. One problem with this arrangement is that when the object is processed with a camera that has a limited field of view, either the camera or the object must be moved in order to locate both marks. Further, two separate images must be acquired and processed, thereby lengthening the processing time to determine the alignment of the object. In addition, the marks occupy space on the object which, in some cases, is at a premium. Further, additional time is required during the manufacturing process to place additional marks on each object.
Therefore, there is a need for a method and apparatus that can quickly and accurately determine the alignment of an object using fiducial marks.
In accordance with the principles of the present invention, a single non-rotationally symmetric fiducial marks is placed on an object and the alignment of the object is determined with a vision tool that can align objects with both angular orientation and translation. Alternatively, if a unique non-rotationally symmetric feature occurs naturally on the object, that feature may be used instead of a fiducial mark. In one embodiment, a geometrical feature matching vision tool is used to locate the single fiducial mark.
In another embodiment, a normalized correlation search tool is used to locate the mark. The tool internally generates a set of rotated and scaled patterns that are then stored. The stored patterns are subsequently used to perform the search.
In still another embodiment, a normalized correlation search tool internally generates a set of rotated and scaled patterns at runtime when the search for the mark is being performed.